package 左哥算法.compare.二叉树;

import java.io.*;
import java.util.*;

public class ch01二叉树的结构 {
    public static StringBuilder fun2(String tree,String[] conditions){
        HashMap<Integer, Node> map = new HashMap<Integer, Node>();
        Node root = new Node();
        String[] arr1 = tree.split(" ");
        root.data = Integer.parseInt(arr1[0]);
        root.fa = null;
        map.put(root.data, root);
        for (int i = 1; i < arr1.length; i++) {
            Node temp = new Node();
            temp.data = Integer.parseInt(arr1[i]);
            map.put(temp.data, temp);
            insert(root, temp);
        }
        int a, b;
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < conditions.length; i++) {
            String[] s = conditions[i].split(" ");
            try {
                switch (s.length) {
                    case 4: // root
                        a = Integer.valueOf(s[0]);
                        if (map.get(a).fa == null) {
                            sb.append("Yes\n");
                        } else {
                            sb.append("No\n");
                        }
                        break;
                    case 5:// siblings
                        a = Integer.valueOf(s[0]);
                        b = Integer.valueOf(s[2]);
                        if (map.get(a).fa == map.get(b).fa) {
                            sb.append("Yes\n");
                        } else {
                            sb.append("No\n");
                        }
                        break;
                    case 6:
                        a = Integer.valueOf(s[0]);
                        b = Integer.valueOf(s[5]);
                        if (map.get(b).fa.data == a) {
                            sb.append("Yes\n");
                        } else {
                            sb.append("No\n");
                        }
                        break;
                    case 7:
                        a = Integer.valueOf(s[0]);
                        b = Integer.valueOf(s[6]);
                        if (s[3].equals("left")) {
                            if (map.get(b).left.data == a) {
                                sb.append("Yes\n");
                            } else {
                                sb.append("No\n");
                            }
                        } else {
                            if (map.get(b).right.data == a) {
                                sb.append("Yes\n");
                            } else {
                                sb.append("No\n");
                            }
                        }
                        break;
                    case 8:
                        a = Integer.valueOf(s[0]);
                        b = Integer.valueOf(s[2]);
                        int count = 0;
                        Node current = map.get(a);
                        while (current.fa != null) {
                            count++;
                            current = current.fa;
                        }
                        current = map.get(b);
                        while (current.fa != null) {
                            count--;
                            current = current.fa;
                        }
                        if (count == 0) {
                            sb.append("Yes\n");
                        } else {
                            sb.append("No\n");
                        }
                        break;
                    default:
                        break;
                }
            } catch (Exception e) {
                sb.append("No\n");
            }
        }
        return sb;
    }

    static class Node {
        int data;
        Node fa = null;
        Node left = null;
        Node right = null;
    }

    static void insert(Node root, Node val) {
        if (val.data < root.data) {
            if (root.left == null) {
                root.left = val;
                val.fa = root;
            } else {
                insert(root.left, val);
            }
        } else {
            if (root.right == null) {
                root.right = val;
                val.fa = root;
            } else {
                insert(root.right, val);
            }
        }
    }

    public static void compare(Fun fun) {
        int count = 100000;
        int k=100;
        while (count-- > 0) {
            int n = r.nextInt(50) + 1;
            Set<Integer> set = new HashSet<>();
            while (set.size() < n) {
                set.add(r.nextInt(100));
            }
            StringBuilder sb = new StringBuilder();
            for (Integer i : set) {
                sb.append(i).append(" ");
            }
            String[] conditions=new String[r.nextInt(50) + 1];
            for (int i = 0; i < conditions.length; i++) {
                conditions[i]=getConditions();
            }
            StringBuilder fun1 = fun.fun(sb.toString(), conditions);
            StringBuilder fun2 = fun2(sb.toString(), conditions);
            if (!fun1.toString().equals(fun2.toString())){
                System.out.println("-----------error--------------");
                System.out.println(sb);
                System.out.println(Arrays.toString(conditions));
                System.out.println("预期：");
                System.out.println(fun2);
                System.out.println("实际：");
                System.out.println(fun1);
            }
        }
        System.out.println("ok");
    }

    static Random r = new Random();
    static String[] base = {
            "${1} is the root",
            "${1} and ${2} are siblings",
            "${1} is the parent of ${2}",
            "${1} is the left child of ${2}",
            "${1} is the right child of ${2}",
            "${1} and ${2} are on the same level",
    };

    public static String getConditions() {
        int i = r.nextInt(base.length);
        if (i == 0) {
            return base[i].replace("${1}", r.nextInt(100) + "");
        } else {
            String res = base[i].replace("${1}", r.nextInt(100) + "");
            return res.replace("${2}", r.nextInt(100) + "");
        }
    }

    public static interface Fun {
        public StringBuilder fun(String tree, String[] condition);
    }
}
